package com.qzh.utils;

public class Sort {
    /**

     排序法	最好情形	平均时间	最差情形	稳定度	空间复杂度
     冒泡排序	O(n)	O(n^2)	O(n^2)	稳定	O(1)
     快速排序	O(nlogn)	O(nlogn)	O(n^2)	不稳定	O(nlogn)
     直接插入排序	O(n)	O(n^2)	O(n^2)	稳定	O(1)
     希尔排序


     不稳定	O(1)
     直接选择排序	O(n^2)	O(n^2)	O(n^2)	不稳定	O(1)
     堆排序	O(nlogn)	O(nlogn)	O(nlogn)	不稳定	O(nlogn)
     归并排序	O(nlogn)	O(nlogn)	O(nlogn)	稳定	O(n)

     */
    /**
     * 冒泡排序
     */
   public static int[] BubbleSort(int[] data){
       for (int i = 0; i < data.length; i++) {
           for (int j = 0; j < data.length-i-1; j++) {
                    if(data[j]>data[j+1])
                    {
                        int temp = data[j+1];
                        data[j+1] = data[j];
                        data[j] = temp;
                    }
           }
       }
       return data;
   }

    /**
     * 快速排序
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int[] Quicksort(int[] arr, int start, int end) {

        if(start < end) {
            // 把数组中的首位数字作为基准数
            int stard = arr[start];
            // 记录需要排序的下标
            int low = start;
            int high = end;
            // 循环找到比基准数大的数和比基准数小的数
            while(low < high) {
                // 右边的数字比基准数大
                while(low < high && arr[high] >= stard) {
                    high--;
                }
                // 使用右边的数替换左边的数
                arr[low] = arr[high];
                // 左边的数字比基准数小
                while(low < high && arr[low] <= stard) {
                    low++;
                }
                // 使用左边的数替换右边的数
                arr[high] = arr[low];
            }
            // 把标准值赋给下标重合的位置
            arr[low] = stard;
            // 处理所有小的数字
            Quicksort(arr, start, low);
            // 处理所有大的数字
            Quicksort(arr, low + 1, end);
        }
        return arr;
    }

    /**
     * 直接插入排序
     * 主要思想是将将前面的数据作为有序的，然后遍历之后的数据，将之后的每一条插入到前面的有序组中
     * 3,2,1,5,4
     *
     * @param arr
     * @return
     */
    public static int[] InsertSort(int[] arr) {
        // 遍历所有数字
        for(int i = 1; i < arr.length - 1; i++) {
            // 当前数字比前一个数字小
            if(arr[i] < arr[i - 1]) {
                int j;
                // 把当前遍历的数字保存起来
                int temp = arr[i];
                for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
                    // 前一个数字赋给后一个数字
                    arr[j + 1] = arr[j];
                }
                // 把临时变量赋给不满足条件的后一个元素
                arr[j + 1] = temp;
            }
        }
        return arr;
    }
    /**
     * 希尔排序
     * 将数组划分为若干个区域，每个区域执行直接插入排序
     *主要思想是将将前面的数据作为有序的，然后遍历之后的数据，将之后的每一条插入到前面的有序组中
     *3,2,1,5,4,8,7,6,9
     * @param arr
     * @return
     */
    public void DividedInsertSort(int[] arr) {
        //步长
        int gap = arr.length/2;
        int[] sub = new int[gap];
            for(int j = 0; j<=arr.length-gap-1; j++)//需要执行数组长度-步长的次数才能排序完全部的，利用了插入排序对顺序数组效率高的特点
            {
                    System.arraycopy(arr, j,sub,0,gap);
                    sub = InsertSort(sub);
            }

    }















}
